/*

埃氏筛的全名是埃拉托斯特尼筛法（Sieve of Eratosthenes）

明确两个概念：
（1）素数（质数）：在大于一的自然数中，除了一和本身以外没有其他的因数
（2）合数（素数的反面）：在大于一的自然数中，除了一和本身以外还有其他的因数

思路：从2开始遍历每一个数
（1）如果是素数，就找出这个素数所有的倍数，筛掉这些数（合数）
（2）如果是合数，就直接筛掉

代码思路
（1）初始化一个数组，初始化为0，默认全部数是素数，之后开始筛选，不是素数的就打标记
（2）核心思想：用数组下标来表示遍历的数，这个数的下标对应的值就表示是不是素数
（3）往后筛选，例如：第一次遍历的（i：2），之后（2*i，3*i，4*i.....）都是合数，这里用循环实现对合数打标记


重点！！！
对于!prime[i]的理解容易偏差

prime[i]本身初始化为0，非0就表示真，也就是说prime[i]这个条件为真，条件成立

理解偏差：认为非0就是真，值就是从0变成1，其实并不会变，prime[i]的值还是0，实际上表示这个条件成立

那如果是prime[i]呢？
prime[i]初始化为0，就表示这个条件不成立，即表示不是素数（是合数），这个时候就没有必要打标记了，
因为在素数的时候已经打过标记了，无需重复标记

例如：
素数2：打标记的数是4,6,8
遍历到合数4：如果打标记，8就被标记了两次，重复了，时间效率降低


*/

#include <stdio.h>

int main()
{
    int prime[1000] = {0}; // 初始化：假设这一百万个数都是素数

    int n, ans = 0; // 统计质数的个数

    scanf("%d", &n);
    printf("\n");
    for (int i = 2; i <= n; i++)
    {
        if (!prime[i])
        {
            ans += 1;
            for (int j = 2 * i; j <= n; j = j + i) // j+i就表示，两倍的i，三倍的i，四倍的i...........
            {
                prime[j] = 1; // 找出合数，打标记
            }
            printf("%-8d\n\t", i); // 把素数打印出来（控制输出格式，C语言默认是右对齐，这里调整为左对齐）
        }
        else
        {
            ; // 如果是合数，啥也不做，要筛选的是质数，用质数的倍数找出合数然后打标记，达到筛选的目的
        }
    }
    printf("\n");
    printf("total number: %d\n", ans);
}
